package com.nanbei.stack;

import org.junit.Test;

import java.util.LinkedList;

/**
 * @ClassDescription:
 * @JdkVersion: 17
 * @Author: BaoShan.li
 * @Created: 2023/11/24 15:59
 */
public class LinkStackTest {

    @Test
    public void test1(){
        LinkStack<Integer> integers = new LinkStack<Integer>(3);
        integers.push(1);
    }

    @Test
    public void test2(){
        ArrayStack<Integer> integers = new ArrayStack<Integer>(3);
        integers.push(1);
        integers.push(2);
        integers.push(3);
        integers.push(4);
        for(int i : integers){
            System.out.println(i);
        }
    }

    /**
     * 中缀表达式转后缀表达式  512+4*+3-
     */
    @Test
    public void test3(){
        String s = "5+((1+2)*4)-3";

        LinkedList<Character> stack = new LinkedList<>();
        StringBuilder sb = new StringBuilder();

        char[] chars = s.toCharArray();

        for (char cha : chars) {
            switch (cha){
                case '+':
                case '*':
                case '-':
                case '/':
                    //先判断栈是否为空
                    if (!stack.isEmpty()){
                        //将栈中优先级比当前优先级小的字符全部输出出来并添加在字符在尾部
                        if ( getHeight(cha) <= getHeight(stack.peek())){
                            while (!stack.isEmpty() && getHeight(cha) <= getHeight(stack.peek())){
                                char item = stack.pop();
                                sb.append(item);
                            }
                            // 将当前字符串入栈
                            stack.push(cha);
                        }else {
                            // 如果当前优先级最大则直接入栈
                            stack.push(cha);
                        }
                    }else {
                        //栈空则直接入栈
                        stack.push(cha);
                    }
                    break;
                case '(':
                    stack.push(cha);
                    break;
                case ')':
                    // 需要将'(' 字符前的全部字符输出添加到字符串尾部
                    while (!stack.isEmpty() && stack.peek() != '('){
                        sb.append(stack.pop());
                    }
                    stack.pop();
                    break;
                default:
                    // 数字则直接入栈
                    sb.append(cha);
            }
        }
        while (!stack.isEmpty()){
            // 将栈中剩余字符串全部输出
            sb.append(stack.pop());
        }
        System.out.println(sb.toString());

    }


    /**
     * 字符 获取优先级
     * @param c char 字符
     * @return 优先级
     */
    public int getHeight(Character c){
        if (c=='+'||c=='-'){
            return 1;
        }else if (c=='*'||c=='/'){
            return 2;
        }else {
            return 0;
        }
    }
}
